﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace MinimumSpanningTrees
{
    public class LazyPrimMST
    {
        //private bool[] marked;//最小生成树的顶点
        //private Queue<Edge> mst;//最小生成树的边
        //private MinPQ<Edge> pq;//横切边（包括失效的边）

        //public LazyPrimMST(EdgeWeightedGraph G)
        //{
        //    pq = new MinPQ<Edge>();
        //    marked = new bool[G.V()];
        //    mst = new Queue<Edge>();

        //    Visit(G,0);
        //    while (!pq.Count > 0)
        //    {
        //        Edge e = pq.Dequeue();

        //        int v = e.Either();
        //        int w = e.Other(v);
        //        if (marked[v] && marked[w])
        //            continue;
        //        pq.Enqueue(e);

        //        if (!marked[v])
        //            Visit(G,v);
        //        if (!marked[w])
        //            Visit(G,w);
        //    }
        //}

        //private void Visit(EdgeWeightedGraph G, int v)
        //{
        //    marked[v] = true;
        //    foreach (Edge e in G.Adj(v))
        //    {
        //        if (!marked[e.Other(v)])
        //            pq.Enqueue(e);
        //    }
        //}

        //public IEnumerable<Edge> Edges()
        //{
        //    return mst;
        //}

        //public double Weight()
        //{
        //    return mst.Sum(o=>o.Weight());
        //}
    }
}
